//现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。 
//
// 给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 
//prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。 
//
// 请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。 
//
// 可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。 
//
// 
//
// 示例 1： 
//
// 
//输入: numCourses = 2, prerequisites = [[1,0]] 
//输出: [0,1]
//解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1]。 
//
// 示例 2： 
//
// 
//输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出: [0,1,2,3] or [0,2,1,3]
//解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是
// [0,1,2,3]。另一个正确的排序是 [0,2,1,3]。
// 
//
// 示例 3： 
//
// 
//输入: numCourses = 1, prerequisites = [] 
//输出: [0]
//解释: 总共 1 门课，直接修第一门课就可。 
//
// 
//
// 提示： 
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// prerequisites 中不存在重复元素 
// 
//
// 
//
// 
// 注意：本题与主站 210 题相同：https://leetcode-cn.com/problems/course-schedule-ii/ 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 59 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2025-04-15 10:04:59
 * @description LCR 113.课程表 II
 
 */
 
public class QA2IGt {
    public static void main(String[] args) {
    //测试代码
    QA2IGt fun = new QA2IGt();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<List<Integer>> edge;
    //是否访问
    int [] vis;
    //结果
    int[] res;
    //全局是否有环
    boolean valid;
    //结果的下标
    int index;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        res = new int[numCourses];
        edge=new ArrayList<>();
        valid=true;
        vis=new int[numCourses];
        index=numCourses-1;
        //至少有这么多条边
        for (int i = 0; i < numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        //把每一个课程的前置课程加进去
        for (int[] prerequisite : prerequisites) {
            edge.get(prerequisite[1]).add(prerequisite[0]);
        }
        //把每一个没搜索的点进行dfs
        for (int i = 0; i < numCourses; i++) {
            if(vis[i]==0){
                dfs(i);
            }
        }
        //有环就算了
        if(!valid){
            return new int[0];
        }
        return res;

    }

    private void dfs(int u){
        //搜索中
        vis[u]=1;
        for (int v : edge.get(u)) {
            //没有搜
            if(vis[v]==0){
                //搜他相邻的
                dfs(v);
                //有环
                if(!valid){
                    return;
                }
            }
            //如果搜到搜索中的，说明有环
            else if(vis[v]==1){
                valid=false;
                return;
            }
        }
        //搜完了
        vis[u]=2;
        //加入到结果中
        res[index--]=u;
    }

    /*从出度入度0开始，bfs*/
    public int[] findOrder1(int numCourses, int[][] prerequisites){
        Queue<Integer> q=new LinkedList<>();
        edge=new ArrayList<>();
        vis=new int[numCourses];
        res=new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            edge.get(prerequisite[1]).add(prerequisite[0]);
            vis[prerequisite[0]]++;
        }

        for (int i = 0; i < numCourses; i++) {
            //把入度为0的点加入队列
            if(vis[i]==0){
                q.offer(i);
            }
        }
        int count=0;
        while (!q.isEmpty()){
            ++count;
            int u =q.poll();
            res[index++]=u;
            for (int v : edge.get(u)) {
                //v的入度-1,减的u
                --vis[v];
                if(vis[v]==0){
                    q.offer(v);
                }
            }
        }
        return count==numCourses?res:new int[0];

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
